package com.jhy.szl.daima20240814;

import com.jhy.suixianglu.daima20221212.ListNode;

/**
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 */
public class GetIntersectionNode {
    public ListNode getIntersectionNode(ListNode A, ListNode B) {
        // 先算出每一个节点的长度
        ListNode headA = A;
        ListNode headB = B;
        int lenA = 0;
        while (headA != null) {
            headA = headA.next;
            lenA++;
        }

        int lenB = 0;
        while (headB != null) {
            headB = headB.next;
            lenB++;
        }
        // 由于刚刚获取长度 所以这里我们要重新指定
        headB = B;
        headA = A;
        if (lenA < lenB) {
            // 交换
            ListNode temp = headA;
            headA = headB;
            headB = temp;
            int tempLen = lenA;
            lenA = lenB;
            lenB = tempLen;
        }

        for (int i = 0; i < lenA - lenB; i++) {
            headA = headA.next;
        }
        while (headA != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}

